/**
 * 461. 汉明距离
 */
public class Solution_461 {
    /**
     * 布赖恩·克尼根算法
     * 当我们在 number 和 number-1 上做 AND 位运算时，
     * 原数字 number 的最右边等于 1 的比特会被移除。
     * 
     * 例如：
     *             x = 1000 1000
     *         x - 1 = 1000 0111
     *   x & (x - 1) = 1000 0000
     * 这样只需要 2 次迭代就可以知道 1000 1000 中 1 的位数，而不需要 8 次。
     */
    public int hammingDistance(int x, int y) {
        int ans = 0;
        int xor = x ^ y;
        while (xor != 0) {
            ans ++;
            xor = xor & (xor - 1);
        }
        return ans;
    }

    /**
     * 手动统计异或后1的位数
     */
    public int hammingDistance2(int x, int y) {
        int ans = 0;
        int xor = x ^ y;
        while (xor != 0) {
            if ((xor & 1) == 1) {
                ans ++;
            }
            xor = xor >> 1;
        }
        return ans;
    }

    /**
     * 内置函数
     */
    public int hammingDistance1(int x, int y) {
        // 对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离
        return Integer.bitCount(x ^ y);
    }

    public static void main(String[] args) {
        Solution_461 solution = new Solution_461();
        int ans = solution.hammingDistance(1, 4);
        System.out.println(ans);
    }
}
